Đã từng chơi cho đội U-18 và U-21 Đức, Fritz có trận ra mắt trong màu áo đội tuyển quốc gia vào tháng 10 năm 2006 trong trận thắng 4-1 trước Slovakia.Vào tháng 6 năm sau đó, anh ghi bàn đầu tiên ở đội tuyển quốc gia trong trận thắng 6-0 trước San Marino.

Euro 2008

Fritz được lựa chọn cho 23 gương mặt thi đấu ở Euro 2008 ở Áo và Thuỵ Sĩ vào mùa hè 2008.Anh xuất hiện trong trận đầu tiên của Đức tiếp Ba Lan, trận này Đức thắng 2-0.Anh cũng xuất hiện trong trận đấu thứ hai gặp Croatia, nhưng trận này thua 2-1.